/*
* Authors: Savenko Maria
*           * * *
*           * * *
* This file contains headers for Ramsey algorithm.
* Description of algorithm in summary.pdf page 3.
*/



#include "stdafx.h"

typedef std::list<vertex_list> clique_list;
typedef std::pair<vertex_list, vertex_list> pair_list;


class ramsey_algorithm {
private:
	graph_t g;
	vertex_list independent_set;
    bool find_vertex_by_name (std::string const v_name, vertex_t & vertex);
    void remove_subgraph(vertex_list list);
    void delete_vertex(vertex_t v, graph_t & g_) const;
	void form_curr_i_set(pair_list & p_list, vertex_list & i_set, clique_list & c_blocks);
	bool ramsey(graph_t & g_, pair_list & p_list);
    void divide_into_subgraphs(graph_vertex const v, graph_t & neighbours, graph_t & non_neighbours);
public:
	void print_independent_set() const;
	bool clique_removal();
    ramsey_algorithm(graph_t & g_);
};
